#include <iostream>
#include <vector>
using namespace std;

int PartSort(vector<int>& a, int left, int right)
{
	int k = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[k])
			right--;

		while (left < right && a[left] <= a[k])
			left++;

		swap(a[left], a[right]);
	}
	swap(a[left], a[k]);
	return left;
}

void QuickSort(vector<int>& a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi-1);
	QuickSort(a, keyi+1, end);
}

int main()
{
	vector<int> a = { 1,3,5,6,7,9,2,4,0 };
	QuickSort(a, 0, a.size()-1);
	for (auto e : a)
	{
		cout << e << " ";
	}
	return 0;
}